package bill.java.lab.client.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class HashTableRelated {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<Integer> inputList = new ArrayList<Integer>();
		inputList.add(1);
		inputList.add(2);
		inputList.add(3);
		inputList.add(4);
		inputList.add(5);
		inputList.add(6);
		inputList.add(7);
		inputList.add(8);
		inputList.add(9);
		inputList.add(10);
		inputList.add(11);
		inputList.add(12);
		inputList.add(13);
		inputList.add(14);
		inputList.add(15);

		Set<Set<Integer>> outPutList = new HashSet<Set<Integer>>();
		Integer k = 10;
		sumUp(inputList, outPutList, k);
		System.out.println(outPutList);
	}

	private static void sumUp(List<Integer> inputList,
			Set<Set<Integer>> outPut, Integer k) {

		// reduce the list
		for (Iterator<Integer> iterator = inputList.iterator(); iterator
				.hasNext();) {
			Integer curValue = iterator.next();
			if (curValue == null || curValue.compareTo(k) >= 0
					|| curValue.intValue() * 2 == k) {
				iterator.remove();
			}
		}

		// return condition
		if (inputList.isEmpty()) {
			return;
		}
		if (inputList.size() == 1) {
			return;
		}

		// round 1, put it into the hash structrue
		Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		for (Integer curr : inputList) {
			Set<Integer> set = new HashSet<Integer>();
			set.add(curr);
			map.put(curr, set);
		}

		// round 2.
		for (Integer curr : inputList) {
			// if we can get the compliment from the map, then (current value
			// and the value in the hash) is a good one
			Set<Integer> set = map.get(k.intValue() - curr.intValue());
			if (set != null) {
				if (set.add(curr)) {
					// find a good one. save it.
					outPut.add(set);
				} else {
					// will be redundant, not a valid one
				}
			} else {
				// no compliment
			}
		}
		System.out.println(outPut);

		// recursively do the same thing for the pair
		
		for (Set<Integer> oneGoodSet : outPut) {
			Set<Set<Integer>> tempResult = new HashSet<Set<Integer>>();
			for (Integer newKey : oneGoodSet) {
//				if(newKey.intValue() ==9){
//					System.out.println("stop");
//				}
				
				sumUp(inputList, tempResult, newKey);
//				if(newKey.intValue() ==9){
//				System.out.println(tempResult);
//				}
		    }
		}

	}

}
